Draw an example of a tree on the board.


What are some applications of trees?

	file directory structure
	searching
	expression evaluation


Give a non-recursive definition of a tree.

	set of nodes
	set of directed edges
	one node is root
	every node (except root) connected from exactly one parent


Give a recursive definition of a tree.

	either tree is empty
	or tree is root and zero or more subtrees
	roots of subtrees T1..Tk connected from root


How many edges are there in a tree with N nodes?


What's a parent?


What's a child?


What's a sibling?


What's an ancestor? proper ancestor?


What's a descendant? proper descendant?


What's a path?


What's the length of a path?


What's a leaf?


What's the depth of a node?

	length of path from root


What's the depth of the root?


What's the height of a node?

	length of path to deepest leaf


What's the height of a leaf?


What's the height of a tree?


What's the size of a node?


What's the size of a tree?




How do you implement a tree data structure?


What should be stored in each tree node object?

	a reference to the data stored at the node
	references to the children of the node


How should you store the references to the children?


Draw the tree with nodes containing arrays of child references.


What's the problem with using arrays of child references?


How can you store the child references without a fixed size array?

	first-child/next-sibling
	each node has two links
	one to leftmost child
	one to the next sibling


Draw the tree with nodes containing first-child/next-sibling references.


Write code for a first-child/next-sibling tree.




What does it mean to traverse a tree?


What are some applications of tree traversal?

	print all the values stored in the tree
	search the tree for a particular value
	find the maximum value in a tree
	compute the height of the tree


What's a preorder traversal?


What's a postorder traversal?


Write code for traversals.